package gold.enterprise;

public class Coupang {

    /*
给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，n>1 并且 m≥1）。
每段的绳子的长度记为 k[0]、k[1]、……、k[m-1]。k[0]k[1] … k[m-1]可能的最大乘积是多少？
例如当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到最大的乘积 18。
*/

    /**
     * 割绳子主方法
     * 思路：枚举绳子切分点dp数组，累计去和
     *
     * @param n
     * @return
     */
    public long cutRope(int n) {
        int[] dp = new int[n + 1];  //初始化都为0
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = i;//最差不拆分
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }

        return dp[n];
    }


    /**
     * Find the string in the char matrix without duplication
     * <p>
     * matrix=
     * [
     * ['P','C','O','U'],
     * ['G','N','U','A'],
     * ['V','A','P','V']
     * ]
     * <p>
     * str="COUPANG" , return "true"
     * <p>
     * str="NAVER" , return "false"
     * <p>
     * str="VAPAN" , return "false"
     */

    public int[][] directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    public boolean findStr(char[][] matrix, String strToFind) {
        if (null == matrix) return false;
        if (null == strToFind || strToFind.length() <= 0) return true;
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (visited[i][j] || matrix[i][j] != strToFind.charAt(0))
                    continue;   //TODO:to pre cache matrix char pos

                visited[i][j] = true;
                if (dfs(matrix, visited, strToFind, 1, i, j)) return true;
                visited[i][j] = false;
            }
        }

        return false;
    }

    public boolean dfs(char[][] matrix, boolean[][] visited, String strToFind, int curPos, int x, int y) {
        if (curPos >= strToFind.length()) return true;

        try {
            for (int[] direction : directions) {
                int nextX = x + direction[0], nextY = y + direction[1];
                if (nextX < 0 || nextX >= matrix.length || nextY < 0 || nextY >= matrix[0].length ||
                        visited[nextX][nextY] || matrix[nextX][nextY] != strToFind.charAt(curPos)) continue;

                visited[nextX][nextY] = true;
                if (dfs(matrix, visited, strToFind, curPos + 1, nextX, nextY)) return true;
                visited[nextX][nextY] = false;
            }

        } catch (Exception e) {
            System.out.println(x + ":" + y);
        }
        return false;
    }


    public static void main(String[] args) {
        Coupang solution = new Coupang();
//        System.out.println(solution.cutRope(12));

        char[][] matrix = {{'P', 'C', 'O', 'U'},
                {'G', 'N', 'U', 'A'},
                {'V', 'A', 'P', 'V'}};
        System.out.println(solution.findStr(matrix, "COUPANG"));


    }


}
